/**
 * 整数转罗马数字
 * 七个不同的符号代表罗马数字，其值如下：
 *
 * 符号	值
 * I	1
 * V	5
 * X	10
 * L	50
 * C	100
 * D	500
 * M	1000
 * 罗马数字是通过添加从最高到最低的小数位值的转换而形成的。将小数位值转换为罗马数字有以下规则：
 *
 * 如果该值不是以 4 或 9 开头，请选择可以从输入中减去的最大值的符号，将该符号附加到结果，减去其值，然后将其余部分转换为罗马数字。
 * 如果该值以 4 或 9 开头，使用 减法形式，表示从以下符号中减去一个符号，例如 4 是 5 (V) 减 1 (I): IV ，9 是 10 (X)
 * 减 1 (I)：IX。仅使用以下减法形式：4 (IV)，9 (IX)，40 (XL)，90 (XC)，400 (CD) 和 900 (CM)。
 * 只有 10 的次方（I, X, C, M）最多可以连续附加 3 次以代表 10 的倍数。你不能多次附加 5 (V)，50 (L)
 * 或 500 (D)。如果需要将符号附加4次，请使用 减法形式。
 * 给定一个整数，将其转换为罗马数字。
 */

/**
 * 还是模拟, 没啥好的思路, 想到直接模拟就可以了
 * 我们如何模拟呢?
 * 首先我们可以将数字以正序的方式存入数组中, 为啥这样存呢, 没啥原因, 咋存都可以, 但我们得知道是以正序的方式存入数组的
 * 接下来, 我们要将数字一个一个转化为字母, 为了好映射这些字母, 我们可以用两个字符数组分别来映射这些字符, 我们得和前面的
 * 数组对应起来, 后面就可以正常模拟, 找其中的规律了
 * 时间复杂度 : O(1)
 * 空间复杂度 : O(1)
 */

public class Main {
    public String intToRoman(int num) {

        // 定义num 的位数
        int n = 0;

        // 存放数字的数组
        int[] arr = new int[5];

        // 将数字以正序的方式存入数组
        for (int i = 1; i <= 4; i++) {
            if (num == 0) break;
            arr[i] = num % 10;
            num /= 10;
            n++;
        }

        // 定义字符数组
        // 注意映射, 因为前面的数字数组是以 1 开始存入数字的, 所以我们要将字符数组的第一位置为 ' ', 又因为题目要求
        // 我们在处理后面的字符时, s2 可以将最后一位也置为 ' '
        char[] s1 = {' ', 'I', 'X', 'C', 'M'};
        char[] s2 = {' ', 'V', 'L', 'D', ' '};

        // 字符拼接函数
        StringBuffer s = new StringBuffer();

        for (int i = n; i > 0; i--) {

            // 从后向开始遍历数组, 因为是从高位开始转化字符
            if (arr[i] == 4) {

                // 特殊 4 ,单独处理
                s.append(s1[i]);
                s.append(s2[i]);

            } else if (arr[i] == 9) {

                // 特殊 9 ,单独处理
                // 这种情况要小心数组越界, 必要时可以在字符数组后面多加一个 ' ', 来保证数组不越界
                s.append(s1[i]);
                s.append(s1[i + 1]);

            } else if (arr[i] < 4) {

                // 对于小于 4, 的处理
                while (arr[i] != 0) {
                    s.append(s1[i]);
                    arr[i]--;
                }


            } else {

                // 对于小于 9, 的处理
                // 要先拼接前面的, 将 > 5, < 9 转化为 < 4 的数字, 后面就和上面的 < 4 一样处理
                s.append(s2[i]);
                arr[i] -= 5;

                while (arr[i] != 0) {
                    s.append(s1[i]);
                    arr[i]--;
                }

            }

        }

        // 将结果字符串化
        return s.toString();
    }
}